package search.bst;

import tree.inter.CustTree;

import java.util.Scanner;

public class BinarySortTree implements CustTree {

    private BstNode root;
    private Scanner sc;

    public BinarySortTree() {
        this.sc = new Scanner(System.in);
    }

    public void createBstTree() {
        int data;
        while ((data = sc.nextInt()) != -1) {
            BstNode p = this.root;
            // 如果根节点为空，则将值赋给根节点
            if (p == null) {
                this.setRoot(new BstNode(data, null, null));
            }
            // 找到要新增的节点的双亲节点
            while (p != null) {
                if (data > p.getData()) {
                    if (p.getRightTree() == null) {
                        p.setRightTree(new BstNode(data, null, null));
                        break;
                    }
                    p = p.getRightTree();
                } else if (data < p.getData()) {
                    if (p.getLeftTree() == null) {
                        p.setLeftTree(new BstNode(data, null, null));
                        break;
                    }
                    p = p.getLeftTree();
                } else { // 如果存在相同值，则什么都不做
                    break;
                }
            }
        }
    }

    /**
     * 删除值为key的节点
     * @param bstNode
     * @param key
     */
    public void deleteBstNode(BstNode bstNode, int key) {
        if (this.getRoot() == null) {
            return;
        } else {
            if (bstNode.getData() == key) {
                delateBstNode(bstNode);
            } else if (key > bstNode.getData()) {
                deleteBstNode(bstNode.getRightTree(), key);
            } else {
                deleteBstNode(bstNode.getLeftTree(), key);
            }
        }
    }

    /**
     * 删除节点
     * @param bstNode
     */
    public void delateBstNode(BstNode bstNode) {
        //找到节点的双亲节点
        int side = -1;
        BstNode parent = getParentNode(bstNode.getData());
        BstNode node = this.getRoot();
        if (parent.getLeftTree().getData() == bstNode.getData()){

        }
        if (parent != null) {

        }
    }

    /**
     * 获取双亲节点
     *
     * @param key 要找的节点元素
     * @return 返回双亲节点
     */
    private BstNode getParentNode(int key) {
        BstNode p = this.getRoot();
        while (p != null) {
            if (p.getLeftTree().getData() == key) {
                return p;
            } else if (p.getRightTree().getData() == key) {
                return p;
            }
        }
        return null;
    }

    public void midOrder() {
        midOrder(this.getRoot());
    }

    private void midOrder(BstNode root) {
        if (root.getLeftTree() != null) {
            midOrder(root.getLeftTree());
        }
        System.out.print(root.getData() + " ");
        if (root.getRightTree() != null) {
            midOrder(root.getRightTree());
        }
    }

    public BstNode getRoot() {
        return root;
    }

    public void setRoot(BstNode root) {
        this.root = root;
    }
}
